/**
 * https://leetcode-cn.com/problems/chou-shu-lcof/
 * 我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
 */
function MinHeap(initArr) {
  this.cache = new Set(initArr || []);
  this.heap = [...this.cache];
  this.initHeap();
}

MinHeap.prototype.swap = function (a, b) {
  const temp = this.heap[b];
  this.heap[b] = this.heap[a];
  this.heap[a] = temp;
};

MinHeap.prototype.initHeap = function () {
  const lastNonLeaf = Math.floor(this.size() / 2) - 1;
  for (let i = lastNonLeaf; i >= 0; i--) {
    this.heapifyDown(i);
  }
};

MinHeap.prototype.heapifyUp = function (i) {
  if (i > 0) {
    const parent = Math.ceil(i / 2) - 1;
    if (this.heap[parent] > this.heap[i]) {
      this.swap(parent, i);
      this.heapifyUp(parent);
    }
  }
};

MinHeap.prototype.heapifyDown = function (i) {
  if (i < this.size()) {
    const left = i * 2 + 1;
    const right = i * 2 + 2;
    let smaller = i;
    if (this.heap[left] < this.heap[smaller]) {
      smaller = left;
    }
    if (this.heap[right] < this.heap[smaller]) {
      smaller = right;
    }
    if (smaller !== i) {
      this.swap(smaller, i);
      this.heapifyDown(smaller);
    }
  }
};

MinHeap.prototype.push = function (el) {
  if (this.cache.has(el)) {
    return;
  }
  this.heap.push(el);
  this.cache.add(el);
  this.heapifyUp(this.size() - 1);
};

MinHeap.prototype.delete = function (el) {
  let i = this.heap.indexOf(el);
  if (i > -1) {
    this.swap(i, this.size() - 1);
    this.heap.pop();
    this.heapifyDown(i);
  }
};

MinHeap.prototype.pop = function (el) {
  const size = this.size();
  if (!size) {
    return null;
  }
  this.swap(0, size - 1);
  const res = this.heap.pop();
  this.heapifyDown(0);
  return res;
};

MinHeap.prototype.size = function () {
  return this.heap.length;
};


var nthUglyNumber = function(n) {
  const heap = new MinHeap();
  heap.push(1);
  let result;
  for (let i = 0; i < n; i++) {
      const min = heap.pop();
      result = min;
      heap.push(min * 2);
      heap.push(min * 3);
      heap.push(min * 5);
  }
  return result;
};
